package pd.struct;

import pd.struct.statement.StatementObject;
import java.util.ArrayList;
import java.util.Collection;

/**
 * The ScriptNode class represents a node of a script tree. It has a reference to its parent and can have any number of children. It holds a StatementObject as its value and is inaccessible outside of its package.
 *
 * @author Joshua Swank
 */
class ScriptNode implements Cloneable
{
    /**
     * The node's value, can be null.
     */
    private StatementObject value = null;

    /**
     * The node's parent or null if it doesn't have one.
     */
    private ScriptNode parent = null;

    /**
     * The size of the node's subtree.
     */
    private int size = 1;

    /**
     * A list of the node's children. It's an ArrayList because it will be often referenced by index.
     */
    private final ArrayList<ScriptNode> childList = new ArrayList<ScriptNode>();

    /**
     * Initializes a new script node.
     */
    protected ScriptNode()
    {
    }

    /**
     * Initializes a new script node with a specified value.
     *
     * @param value the value of the new node.
     */
    protected ScriptNode( StatementObject value )
    {
        this.value = value;
    }

    /**
     * Initializes a new script node with a specified value and collection of children.
     *
     * @param value the value of the new node.
     * @param children the children of the new node.
     */
    protected ScriptNode( StatementObject value, Collection<ScriptNode> children )
    {
        this.value = value;

        addChildren( children );
    }

    /**
     * Returns a string representing the node's value.
     *
     * @return the statement held by the node as a string or null if the value is null.
     */
    public String toString()
    {
        if( value != null )
            return value.toString();
        else
            return null;
    }

    /**
     * Adds a new child to the node.
     *
     * @param child the value of the new child.
     */
    protected void addChild( StatementObject child )
    {
        addChild( new ScriptNode( child ));
    }

    /**
     * Adds a collection of children to the node.
     *
     * @param children the children to be added.
     */
    protected final void addChildren( Collection<ScriptNode> children )
    {
        if( children != null )
            for( ScriptNode c : children )
                addChild( c );
    }

    /**
     * Adds a child to the node.
     *
     * @param child the child to be added.
     */
    protected final void addChild( ScriptNode child )
    {
        if( child.parent == null )
        {
            child.parent = this;
            childList.add( child );
            addSize( child.size );
        }
    }

    /**
     * Removes a child from the node.
     *
     * @param child the child to remove.
     * @return true if the child was removed successfully, false otherwise.
     */
    protected boolean removeChild( ScriptNode child )
    {
        if( child.parent == this )
        {
            child.parent = null;

            if( childList.remove( child ))
            {
                addSize( -child.size );
                return true;
            }
        }

        return false;
    }

    /**
     * Removes the child at the specified index.
     *
     * @param index the index of the child to be removed.
     * @return the value of the removed child or null if it doesn't exist.
     */
    protected StatementObject removeChild( int index )
    {
        if( childExists( index ))
            return childList.remove( index ).getValue();
        else
            return null;
    }

    /**
     * Sets the value of the node.
     *
     * @param value the node's new value.
     */
    protected void setValue( StatementObject value )
    {
        this.value = value;
    }

    /**
     * Returns the node's value.
     *
     * @return the value held by the node.
     */
    protected StatementObject getValue()
    {
        return (StatementObject)value.clone();
    }

    /**
     * Returns the size of the node's subtree.
     *
     * @return the size of the subtree.
     */
    protected int getSize()
    {
        return size;
    }

    /**
     * Returns the node's child count.
     *
     * @return the node's child count.
     */
    protected int getChildCount()
    {
        return childList.size();
    }

    /**
     * Returns true if the node has children.
     *
     * @return true if the node has at least one child.
     */
    protected boolean hasChildren()
    {
        return !childList.isEmpty();
    }

    /**
     * Returns true if the node has a parent.
     *
     * @return true if the node has a parent, false otherwise.
     */
    protected boolean hasParent()
    {
        return ( parent != null );
    }

    /**
     * Returns the parent node.
     *
     * @return the parent node or null if the node has no parent.
     */
    protected ScriptNode getParent()
    {
        return parent;
    }

    /**
     * Returns the subtree with the node as the root.
     *
     * @return the subtree with the node as the root.
     */
    protected ScriptTree getSubtree()
    {
        return new ScriptTree( cloneSubtree() );
    }

    /**
     * Returns true if a child exists at the specified index.
     *
     * @param index the index of the child.
     * @return true if a child exists at the specified index, false otherwise.
     */
    protected boolean childExists( int index )
    {
        return ( index >= 0 && index < childList.size() );
    }

    /**
     * Returns the child at the specified index.
     *
     * @param index the position of the child.
     * @return the child at the specified index or null if it doesn't exist.
     */
    protected ScriptNode getChild( int index )
    {
        if( childExists( index ))
            return childList.get( index );
        else
            return null;
    }

    /**
     * Returns the index of a child of the node.
     *
     * @param child the child whose index is retrieved.
     * @return the index of the child or -1 if it isn't a child of the node.
     */
    protected int getChildIndex( ScriptNode child )
    {
        return childList.indexOf( child );
    }

    /**
     * Returns the node's position relative to its siblings.
     *
     * @return the node's position relative to its siblings or -1 if it has no parent.
     */
    protected int getChildIndex()
    {
        if( parent != null )
            return parent.getChildIndex( this );
        else
            return -1;
    }

    /**
     * Returns the sibling in front of the node.
     *
     * @return the sibling in front of the node or null if there isn't one.
     */
    protected ScriptNode getNextSibling()
    {
        int index = getChildIndex();

        if( index >= 0 )
            return parent.getChild( index + 1 );
        else
            return null;
    }

    /**
     * Returns true if the node has a sibling in front of itself.
     *
     * @return true if there is one ore more sibling in front of the node, false otherwise.
     */
    protected boolean hasNextSibling()
    {
        int index = getChildIndex();

        if( index >= 0 )
            return ( index + 1 < parent.getChildCount() );
        else
            return false;
    }

    /**
     * Returns true if the node has a sibling behind itself.
     *
     * @return true if there is one ore more sibling behind of the node, false otherwise.
     */
    protected boolean hasPreviousSibling()
    {
        return ( getChildIndex() >= 1 );
    }

    /**
     * Returns the sibling behind the node.
     *
     * @return the sibling behind the node or null if there isn't one.
     */
    protected ScriptNode getPreviousSibling()
    {
        int index = getChildIndex();

        if( index > 0 )
            return parent.getChild( index - 1 );
        else
            return null;
    }

    /**
     * Removes the node from the tree and returns its parent.
     *
     * @return the parent node or null if there is no parent.
     */
    protected ScriptNode remove()
    {
        if( parent != null )
        {
            ScriptNode p = parent;
            parent.removeChild( this );
            return p;
        } else
            return null;
    }

    /**
     * Returns the leftmost leaf of the node's subtree.
     *
     * @return the leftmost leaf of the node's subtree.
     */
    protected ScriptNode toLeft()
    {
        if( hasChildren() )
            return childList.get( 0 ).toLeft();
        else
            return this;
    }

    /**
     * Returns the rightmost leaf of the node's subtree.
     *
     * @return the rightmost leaf of the node's subtree.
     */
    protected ScriptNode toRight()
    {
        if( hasChildren() )
            return childList.get( childList.size() - 1 ).toRight();
        else
            return this;
    }

    /**
     * Returns the next node in a preorder traversal.
     *
     * @return the next node using preorder traversal or null if there isn't one.
     */
    protected ScriptNode nextPreorder()
    {
        if( !childList.isEmpty() )
            return getChild( 0 );
        else
        {
            ScriptNode current = this;

            while( !current.hasNextSibling() && current.parent != null )
                current = current.parent;

            if( current.hasNextSibling() )
                return current.getNextSibling();
            else
                return null;
        }
    }

    /**
     * Returns the next node in a postorder traversal.
     *
     * @return the next node using postorder traversal or null if there isn't one.
     */
    protected ScriptNode nextPostorder()
    {
        if( hasNextSibling() )
            return getNextSibling().toLeft();
        else if( parent != null )
            return parent;
        else
            return null;
    }

    /**
     * Creates a clone of the node and its descendents.
     *
     * @return the root of the new subtree.
     */
    protected ScriptNode cloneSubtree()
    {
        ScriptNode newRoot = clone();

        for( ScriptNode child : childList )
            newRoot.addChild( child.cloneSubtree() );

        return newRoot;
    }

    /**
     * Creates a copy of the node with no relatives and a cloned value.
     *
     * @return a clone of the node.
     */
    protected ScriptNode clone()
    {
        return new ScriptNode( value.clone() );
    }

    /**
     * Returns the depth of the node.
     *
     * @return the depth of the node.
     */
    protected int getDepth()
    {
        ScriptNode n = parent;
        int depth = 1;

        while( n != null )
        {
            n = n.parent;
            depth++;
        }

        return depth;
    }

    /**
     * Returns an array containing the positions of the node's previous n ancestors using the specified traversal method.
     *
     * @param n the number of ancestors to retrieve.
     * @param method the method used to determine each ancestor's position.
     * @return an array of length min( depth-1, n ) containing the positions of the node's ancestors or null if n < 0.
     */
    protected int[] getAncestorPositions( int n, Traversal method )
    {
        ScriptNode[] ancestors = getAncestors( n );

        if( ancestors != null )
        {
            int[] positions = new int[ancestors.length];

            for( int i = 0; i < positions.length; i++ )
                positions[i] = ancestors[i].getPosition( method );

            return positions;
        }
        else
            return null;
    }

    /**
     * Returns an array containing the values of the node's previous n ancestors.
     *
     * @param n the number of ancestors to retrieve.
     * @return an array of length min( depth-1, n ) containing the values of the node's ancestors or null if n < 0.
     */
    protected StatementObject[] getAncestorValues( int n )
    {
        ScriptNode[] ancestors = getAncestors( n );

        if( ancestors != null )
        {
            StatementObject[] values = new StatementObject[ancestors.length];

            for( int i = 0; i < values.length; i++ )
                values[i] = ancestors[i].getValue();

            return values;
        }
        else
            return null;
    }

    /**
     * Gets the position of the node using the specified traversal.
     *
     * @param method the traversal method used to find the position.
     * @return the position of the node using the specified traversal.
     */
    protected int getPosition( Traversal method )
    {
        switch( method )
        {
            case PREORDER:
                return getPreorderPosition();

            case POSTORDER:
                return getPostorderPosition();

            default:
                return -1;
        }
    }

    /**
     * Returns the position of the node using postorder traversal.
     *
     * @return the position of the node using postorder traversal.
     */
    private int getPostorderPosition()
    {
        ScriptNode current = this;
        int position = size;

        while( current.hasParent() )
        {
            while( current.hasPreviousSibling() )
            {
                current = current.getPreviousSibling();
                position += current.getSize();
            }

            current = current.getParent();
        }

        return position;
    }

    /**
     * Returns the position of the node using preorder traversal.
     *
     * @return the position of the node using preorder traversal.
     */
    private int getPreorderPosition()
    {
        ScriptNode current = this;
        int position = 1;

        while( current.hasParent() )
        {
            while( current.hasPreviousSibling() )
            {
                current = current.getPreviousSibling();
                position += current.getSize();
            }

            current = current.getParent();
            position++;
        }

        return position;
    }

    /**
     * Adds the specified value to the node's size.
     *
     * @param change the change in the node's size.
     */
    private void addSize( int change )
    {
        size += change;

        if( parent != null )
            parent.addSize( change );
    }

    /**
     * Returns an array containing the node's previous n ancestors.
     *
     * @param n the number of ancestors to retrieve.
     * @return an array of length min( depth-1, n ) containing the node's ancestors or null if n < 0.
     */
    private ScriptNode[] getAncestors( int n )
    {
        if( n >= 0 )
        {
            int depth = getDepth();
            ScriptNode[] ancestors;
            ScriptNode c = this;

            ancestors = new ScriptNode[Math.min( depth-1, n )];

            for( int i = 0; i < ancestors.length; i++ )
            {
                c = c.parent;
                ancestors[i] = c;
            }

            return ancestors;
        }
        else
            return null;
    }
}